home *** CD-ROM | disk | FTP | other *** search
- Path: newsbf02.news.aol.com!not-for-mail
- From: mvaccaro1@aol.com (MVaccaro1)
- Newsgroups: comp.lang.c
- Subject: Re: Newbie needs help w/ recursion
- Date: 19 Mar 1996 10:56:18 -0500
- Organization: America Online, Inc. (1-800-827-6364)
- Sender: root@newsbf02.news.aol.com
- Message-ID: <4imlf2$osh@newsbf02.news.aol.com>
- References: <4ikq6p$io1@impsets.dash.com>
- Reply-To: mvaccaro1@aol.com (MVaccaro1)
- NNTP-Posting-Host: newsbf02.mail.aol.com
-
- >Hi, I am new and am about to pull my hair out over the supposedly simple
- >recursion problem I have. The function is to take a number and raise it
- >to a neg or pos power and return the value to main(). I need to take
- >the following and make it a recursive function...
-
- >double power (double a, float b)
- > {
- > double power = 1;
- > int i;
- .
- .
- .
-
- Dianna,
-
- Recursive programming requires thinking along the lines of step wise tasks
- until
- some point is reached where the task is done. To use your power function,
- examine the problem this way:
-
- x raised to the power of 0 is 1 /* this is the end of the task chain */
- x raised to the power of 1 is x times x raised to the power of 0
- x raised to the power of 2 is x times x raised to the power of 1
- .
- .
- .
- x raised to the power of n is x times x raised to the power of n-1.
-
- thus, in psuedo code, a recursive function of this nature would look like
- this:
-
- function ( x, n )
- if n is greater than 0
- return x * function( x, n - 1 );
- else
- return 1
- endfunction
-
- or in C
-
- double power( double x, int n )
- {
- if ( n > 0 )
- return x * power( x, n- 1 );
- else
- return 1;
- }
-
- Let x = 2 and n = 2 when the function is first called. The first time
- through
- the statement "return x * power( x, n - 1);" will be executed which means
- that
- the function power( x, n - 1 ) must be evaluated first before the return
- can be
- executed. Thus we enter power a second time (recursively) with x = 2 and
- n = 1.
- This second time with n = 1, the statement "return x * power( x, n - 1 );"
- is
- executed with the function power being entered a third time. In the third
- iteration
- of power, n is now equal to 0 causing the third iteration to return 1. 1
- is
- returned to the second iteration which was in the process of a return
- statement.
- The second iteration returns 2 ( x = 2 and power( x, n-1 ) = 1) so 2 * 1 =
- 2).
- The second iteration returns to the first iteration which was also in the
- process
- of executing a return. Now the first iteration's return is 2 * 2, (x=2 and
- power(x , n - 1) = 2 this time around). The function power finally
- returns a
- value of 4.
-
- Handling negative numbers requires additional code as follows:
-
- double power( double x, int n )
- {
- if ( n > 0 )
- return x * power( x, n- 1 );
- else if ( n < 0 )
- return ( 1/x ) * power( x, n + 1 );
- else
- return 1;
- }
-
- Thus when n is -2, 0.25 is returned. Handling fractional exponentiation
- is beyound
- the scope of my own laziness but I think you get the idea.
-
- I hope this helps.
-
- Mike:->
-
- Design? What design! - I've too much coding to do...
-